The present invention relates generally to data routing systems, and more particularly to a method and apparatus for routing packets through a high speed data switch.
In packet switched communication systems, a router (switch or packet forwarding engine) is a switching device which receives packets on one port, and based on destination information contained within the packet, routes the packet to the destination (or intermediary destination) via another port. Prior art routers perform this routing function by evaluating header information associated with a first data block in the packet in order to determine the proper output port for a particular packet. The evaluation process involves two basic steps performed sequentially: key extraction and route look-up.
Each packet contains a header and data field. The header field contains control information associated with the routing of the packet, including source and destination information. The data field contains information which may include embedded headers for higher level protocols. The first step of the routing process is the identification of the key. The key contains the information that is used to look-up the route for an incoming packet. Upon identifying the key associated with an incoming packet, the router next must determine which port provides the best path to the destination.
Associated with the router is a route table. The route table includes entries having a route and destination associated therewith. After a key for a packet has been determined, the router performs a look-up in the route table for the destination associated with that key to determine the output port for the packet. The key may match multiple routes in the route table. Assuming the router located a match of the key in the route table, the entire packet is thereafter routed to the destination via the indicated output port.
In the prior art, the process of performing the look-up in a large route table was a very time consuming process. In order to speed the look-up process, caching of the most recent route matches was often performed. However, caching is minimally effective, providing an advantage only if the same key patterns are repeated.
In addition, the process of changing a route in an existing route table was difficult in prior art systems, often requiring the disruption of the look-up process.
Finally, prior art route tables typically provide only route and destination information. The size of the route tables were often minimized to include only minimal information for route look-up. Typically, separate tables were required for unicast and multicast routing. Pejorative information relating to flow identification, packet routing or accounting was not stored in the route tables so as not to slow down the already under-performing look-up engines.